#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
//struct ListNode* FindKthToTail(struct ListNode* pListHead, int k) {
//    struct ListNode* fast = pListHead;
//    struct ListNode* slow = pListHead;
//    while (k--)
//    {
//        if (fast == NULL)
//        {
//            return NULL;
//        }
//        fast = fast->next;
//    }
//    while (fast)
//    {
//        fast = fast->next;
//        slow = slow->next;
//    }
//    return slow;
//}

//struct ListNode* middleNode(struct ListNode* head) {
//    struct ListNode* fast = head;
//    struct ListNode* slow = head;
//    while (fast && fast->next)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//    }
//    return slow;
//}

//struct ListNode* removeElements(struct ListNode* head, int val) {
//    struct ListNode* dst, * cur;
//    dst = NULL;
//    cur = head;
//    while (cur)
//    {
//        if (cur->val != val)
//        {
//            dst = cur;
//            cur = cur->next;
//        }
//        else
//        {
//            if (cur == head)
//            {
//                head = cur->next;
//                free(cur);
//                cur = head;
//            }
//            else
//            {
//                dst->next = cur->next;
//                free(cur);
//                cur = dst->next;
//            }
//        }
//    }
//    return head;
//}
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    int na = 1;
//    int nb = 1;
//    struct ListNode* tailA = headA;
//    struct ListNode* tailB = headB;
//    while (tailA)
//    {
//        tailA = tailA->next;
//        na++;
//    }
//    while (tailB)
//    {
//        tailB = tailB->next;
//        nb++;
//    }
//    int gap = abs(na - nb);
//    struct ListNode* longhead = headA, * slowhead = headB;
//    if (na < nb)
//    {
//        longhead = headB;
//        slowhead = headA;
//    }
//    while (gap--)
//    {
//        longhead = longhead->next;
//    }
//    while (longhead != slowhead)
//    {
//        longhead = longhead->next;
//        slowhead = slowhead->next;
//    }
//    return longhead;
//}

//bool hasCycle(struct ListNode* head) {
//    struct ListNode* slow = head;
//    struct ListNode* fast = head;
//    while (fast != NULL && fast->next != NULL)
//    {
//        fast = fast->next->next;
//        slow = slow->next;
//        if (fast == slow)
//        {
//            return true;
//        }
//    }
//    return false;
//}
struct ListNode* detectCycle(struct ListNode* head) {
    struct ListNode* slow = head;
    struct ListNode* fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast)
        {
            struct ListNode* list1 = head;
            struct ListNode* list2 = fast;
            while (list1 != list2)
            {
                list1 = list1->next;
                list2 = list2->next;
            }
            return list1;
        }
    }
    return NULL;
}